#include"AVL_tree.h"

template<class Record>
Error_code AVL_tree<Record>::insert(const Record& new_data)
{
	bool taller;
	return avl_insert(root, new_data, taller);
}

template<class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>*& sub_root, const Record& new_data, bool& taller)
{
	Error_code result = success;
	if (sub_root == NULL)
	{
		sub_root = new AVL_node<Record>(new_data);
		taller = true;
	}
	else if (new_data == sub_root->data)
	{
		result = duplicate_error;
		taller = false;
	}
	else if (new_data < sub_root->data)
	{
		result = avl_insert(sub_root->left, new_data, taller);
		if(taller == true)
			switch (sub_root->get_balance())
			{
			case left_higher:
				left_balance(sub_root);
				taller = false;
				break;
			case equal_height:
				sub_root->set_balance(left_higher);
				break;
			case right_higher:
				sub_root->set_balance(equal_height);
				taller = false;
				break;
			}
	}
	else
	{
		result = avl_insert(sub_root->right, new_data, taller);
		if(taller == true)
			switch (sub_root->get_balance())
			{
			case left_higher:
				sub_root->set_balance(equal_height);
				taller = false;
				break;
			case equal_height:
				sub_root->set_balance(right_higher);
				break;
			case right_higher:
				right_balance(sub_root);
				taller = false;
				break;
			}
	}
	return result;
}
